package org.usmile.algorithms.leetcode.middle;

import java.util.Random;

/**
 * 912. 排序数组
 *
 * 给你一个整数数组 nums，请你将该数组升序排列。
 * 示例 1：
 * 输入：nums = [5,2,3,1]
 * 输出：[1,2,3,5]
 *
 * 示例 2：
 * 输入：nums = [5,1,1,2,0,0]
 * 输出：[0,0,1,1,2,5]
 *
 * 提示：
 * 1 <= nums.length <= 5 * 104
 * -5 * 104 <= nums[i] <= 5 * 104
 */
public class _0912 {
}

class _0912_Solution {
    public int[] sortArray(int[] nums) {
        if (nums.length <= 1) {
            return nums;
        }
        quickSort(nums, 0, nums.length - 1);

        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int[] p = partition(nums, left, right);
        quickSort(nums, left, p[0] - 1);
        quickSort(nums, p[1] + 1, right);
    }

    private int[] partition(int[] nums, int left, int right) {
        int randomIndex = new Random().nextInt(right - left + 1) + left;
        int pivot = nums[randomIndex];
        int smaller = left;
        int bigger = right;
        int i = left;
        while (i <= bigger) {
            if (nums[i] < pivot) {
                if (i != smaller) {
                    swap(nums, smaller, i);
                }

                i++;
                smaller++;
            } else if (nums[i] == pivot) {
                i++;
            } else {
                swap(nums, bigger, i);

                bigger--;
            }
        }

        return new int[]{smaller, bigger};
    }

    private static void swap(int[] nums, int smaller, int i) {
        int temp = nums[i];
        nums[i] = nums[smaller];
        nums[smaller] = temp;
    }
}